package com.lw.leetcode.greedy.c;

import java.util.Map;
import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 * c
 * greep
 * 2565. 最少得分子序列
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/13 10:47
 */
public class MinimumScore {


    public static void main(String[] args) {
        MinimumScore test = new MinimumScore();

        // 1
//        String s = "abacaba";
//        String t = "bzaa";

//        // 3
//        String s = "cde";
//        String t = "xyz";

//        // 0
        String s = "adebddaccdcabaade";
        String t = "adbae";

        //
//        String s = Utils.getStr(10, 'a', 'z');
//        String t = Utils.getStr(10, 'a', 'z');


        int i = test.minimumScore(s, t);
        System.out.println(i);
    }

    public int minimumScore(String s, String t) {
        int m = s.length();
        int n = t.length();
        char[] ss = s.toCharArray();
        char[] ts = t.toCharArray();
        TreeMap<Integer, Integer> map = new TreeMap<>();
        map.put(m, n);
        int i = m - 1;
        int j = n - 1;
        while (i >= 0 && j >= 0) {
            if (ss[i] == ts[j]) {
                map.put(i, j);
                i--;
                j--;
            } else {
                i--;
            }
        }
        i = 0;
        j = 0;
        Map.Entry<Integer, Integer> entry = map.ceilingEntry(0);
        int min = entry.getValue();
        while (i < m && j < n) {
            if (ss[i] == ts[j]) {
                i++;
                j++;
                int value = map.ceilingEntry(i).getValue();
                if (value <= j) {
                    return 0;
                }
                min = Math.min(min, value - j);
            } else {
                i++;
            }
        }
        return min;
    }

}
